#include <stdio.h>
#include <stdlib.h>

// 定义二叉树节点结构
struct TreeNode {
    int data;                // 数据
    struct TreeNode* left;   // 左子树指针
    struct TreeNode* right;  // 右子树指针
};

// 定义二叉树结构体
struct BinaryTree {
    struct TreeNode* root;  // 根节点指针
};

// 初始化二叉树
void initializeBinaryTree(struct BinaryTree* tree) {
    tree->root = NULL;
}

// 创建新节点
struct TreeNode* createTreeNode(int value) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }

    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;

    return newNode;
}

// 插入节点
struct TreeNode* insertNode(struct TreeNode* root, int value) {
    if (root == NULL) {
        return createTreeNode(value);
    }

    if (value < root->data) {
        root->left = insertNode(root->left, value);
    } else if (value > root->data) {
        root->right = insertNode(root->right, value);
    }

    return root;
}

// 查找节点
struct TreeNode* searchNode(struct TreeNode* root, int value) {
    if (root == NULL || root->data == value) {
        return root;
    }

    if (value < root->data) {
        return searchNode(root->left, value);
    } else {
        return searchNode(root->right, value);
    }
}

// 找到最小节点（最左边的节点）
struct TreeNode* findMinNode(struct TreeNode* root) {
    while (root->left != NULL) {
        root = root->left;
    }
    return root;
}

// 删除节点
struct TreeNode* deleteNode(struct TreeNode* root, int value) {
    if (root == NULL) {
        return root;
    }

    if (value < root->data) {
        root->left = deleteNode(root->left, value);
    } else if (value > root->data) {
        root->right = deleteNode(root->right, value);
    } else {
        // 找到要删除的节点

        // 节点有一个或没有子节点
        if (root->left == NULL) {
            struct TreeNode* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            struct TreeNode* temp = root->left;
            free(root);
            return temp;
        }

        // 节点有两个子节点，找到右子树的最小节点，将其值复制到当前节点，然后删除右子树的最小节点
        struct TreeNode* temp = findMinNode(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }

    return root;
}

// 打印二叉树（中序遍历）
void printBinaryTree(struct TreeNode* root) {
    if (root != NULL) {
        printBinaryTree(root->left);
        printf("%d ", root->data);
        printBinaryTree(root->right);
    }
}

// 释放二叉树内存
void freeBinaryTree(struct TreeNode* root) {
    if (root != NULL) {
        freeBinaryTree(root->left);
        freeBinaryTree(root->right);
        free(root);
    }
}

int main() {
    struct BinaryTree myBinaryTree;
    initializeBinaryTree(&myBinaryTree);

    // 插入一些节点到二叉树
    myBinaryTree.root = insertNode(myBinaryTree.root, 30);
    myBinaryTree.root = insertNode(myBinaryTree.root, 20);
    myBinaryTree.root = insertNode(myBinaryTree.root, 40);
    myBinaryTree.root = insertNode(myBinaryTree.root, 10);
    myBinaryTree.root = insertNode(myBinaryTree.root, 25);

    // 打印二叉树
    printf("Binary Tree (In-order): ");
    printBinaryTree(myBinaryTree.root);
    printf("\n");

    // 查找节点
    int searchValue = 20;
    struct TreeNode* searchResult = searchNode(myBinaryTree.root, searchValue);
    if (searchResult != NULL) {
        printf("Node with value %d found in the binary tree.\n", searchValue);
    } else {
        printf("Node with value %d not found in the binary tree.\n", searchValue);
    }

    // 删除节点
    int deleteValue = 20;
    myBinaryTree.root = deleteNode(myBinaryTree.root, deleteValue);

    printf("Binary Tree after deleting node with value %d (In-order): ", deleteValue);
    printBinaryTree(myBinaryTree.root);
    printf("\n");

    // 释放二叉树内存
    freeBinaryTree(myBinaryTree.root);

    return 0;
}